class Solution {
    public int reversePairs(int[] record) {
        return mer(record,0,record.length-1);
    }

    public int mer(int[] nums,int l,int r){
        if(l>=r) return 0;
        int ret=0;
        int mid=(l+r)/2;
        ret+=mer(nums,l,mid);
        ret+=mer(nums,mid+1,r);
        int[] tmp=new int[r-l+1];
        int cur1=l,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=r){
            if(nums[cur1]<=nums[cur2]) tmp[i++]=nums[cur1++];
            else{
                tmp[i++]=nums[cur2];
                ret+=mid-cur1+1;
                cur2++;
            }
        }

        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=r) tmp[i++]=nums[cur2++];

        for(int j=0;j<(r-l+1);j++) nums[l+j]=tmp[j];
        return ret;

    }
}